{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Linear Stock Score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大线性股票得分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 <strong>1-indexed</strong> 整数数组 <code>prices</code>，其中 <code>prices[i]</code> 是第 <code>i</code> 天某只股票的价格。你的任务是&nbsp;<strong>线性</strong>&nbsp;地选择 <code>prices</code>&nbsp;中的一些元素。</p>\n",
    "\n",
    "<p>一个选择 <code>indexes</code>，其中 <code>indexes</code> 是一个 <strong>1-indexed</strong> 整数数组，长度为 <code>k</code>，是数组 <code>[1, 2, ..., n]</code> 的子序列，如果以下条件成立，那么它是 <strong>线性</strong> 的：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>对于每个 <code>1 &lt; j &lt;= k，prices[indexes[j]] - prices[indexes[j - 1]] == indexes[j] - indexes[j - 1]</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>数组的 <strong>子序列</strong> 是经由原数组删除一些元素（可能不删除）而产生的新数组，且删除不改变其余元素相对顺序。</p>\n",
    "\n",
    "<p>选择 <code>indexes</code> 的 <strong>得分</strong> 等于以下数组的总和：<code>[prices[indexes[1]], prices[indexes[2]], ..., prices[indexes[k]]</code>。</p>\n",
    "\n",
    "<p>返回 <em>线性选择的&nbsp;<strong>最大得分</strong>。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> prices = [1,5,3,7,8]\n",
    "<strong>输出：</strong> 20\n",
    "<strong>解释：</strong> 我们可以选择索引[2,4,5]。我们可以证明我们的选择是线性的：\n",
    "对于j = 2，我们有：\n",
    "indexes[2] - indexes[1] = 4 - 2 = 2。\n",
    "prices[4] - prices[2] = 7 - 5 = 2。\n",
    "对于j = 3，我们有：\n",
    "indexes[3] - indexes[2] = 5 - 4 = 1。\n",
    "prices[5] - prices[4] = 8 - 7 = 1。\n",
    "元素的总和是：prices[2] + prices[4] + prices[5] = 20。 \n",
    "可以证明线性选择的最大和是20。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b> prices = [5,6,7,8,9]\n",
    "<b>输出：</b> 35\n",
    "<b>解释：</b> 我们可以选择所有索引[1,2,3,4,5]。因为每个元素与前一个元素的差异恰好为1，所以我们的选择是线性的。\n",
    "所有元素的总和是35，这是每个选择的最大可能总和。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= prices.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= prices[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-linear-stock-score](https://leetcode.cn/problems/maximum-linear-stock-score/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-linear-stock-score](https://leetcode.cn/problems/maximum-linear-stock-score/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,5,3,7,8]', '[5,6,7,8,9]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUniqueSubarray(self, nums: List[int]) -> int:\n",
    "        if len(set(nums)) == len(nums):\n",
    "            return sum(nums)\n",
    "        \n",
    "        left, right = 0, 1\n",
    "        curSet = set([nums[0]])\n",
    "        maxScore, curScore = nums[0], nums[0]\n",
    "        while right < len(nums):\n",
    "            if nums[right] not in curSet:\n",
    "                curSet.add(nums[right])\n",
    "                # curScore += nums[right]\n",
    "            else:\n",
    "                while nums[left] != nums[right]:\n",
    "                    # print(curSet, '------', nums[left], nums[right], left, right, '1111111')\n",
    "                    curSet.remove(nums[left])\n",
    "                    left += 1\n",
    "                    # print(curSet, nums[left], nums[right], left, right, '2222222')\n",
    "                    \n",
    "                left += 1\n",
    "            right += 1\n",
    "                # curScore = sum(nums[left:right+1])\n",
    "            \n",
    "            # print(curSet, 'zzzz')\n",
    "            maxScore = max(maxScore, sum(curSet))\n",
    "        \n",
    "        return maxScore"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param prices:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = {}\n",
    "        for k,v in enumerate(prices):\n",
    "            tag = v - k\n",
    "            if tag not in m1:\n",
    "                m1[tag] = v\n",
    "            else:\n",
    "                m1[tag] += v\n",
    "        return max(m1.values())\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "        c=defaultdict(int)\n",
    "        for i,p in enumerate(prices):\n",
    "            c[p-i]+=p\n",
    "        return max(c.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "        d=defaultdict(int)\n",
    "        n=len(prices)\n",
    "        for i in range(n):\n",
    "            d[prices[i]-i]+=prices[i]\n",
    "        return max(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "        cnt = Counter()\n",
    "        for i, x in enumerate(prices):\n",
    "            cnt[x - i] += x\n",
    "        return max(cnt.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "\n",
    "        # prices[indexes[j]] - prices[indexes[j - 1]] == indexes[j] - indexes[j - 1]\n",
    "        # prices[indexes[j]] - indexes[j] = prices[indexes[j - 1]] - indexes[j - 1]\n",
    "\n",
    "\n",
    "\n",
    "        dc = Counter()\n",
    "\n",
    "        for i, v in enumerate(prices): dc[v - i] += v\n",
    "\n",
    "        return max(dc.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "        dc = Counter()\n",
    "        for i,v in enumerate(prices): dc[v-i] += v\n",
    "        return max(dc.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "        cnt = Counter()\n",
    "        for i in range(len(prices)):\n",
    "            cnt[prices[i] - i] += prices[i]\n",
    "        return max(cnt.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "        dc = Counter()\n",
    "        for i,v in enumerate(prices): dc[v-i] += v\n",
    "        return max(dc.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "        que = Counter()\n",
    "        for i, j in enumerate(prices):\n",
    "            que[j - i] += j \n",
    "        return max(que.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "        d=defaultdict(int)\n",
    "        for i in range(len(prices)):\n",
    "            d[prices[i]-i]+=prices[i]\n",
    "        return max(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "\n",
    "\n",
    "        dc = Counter()\n",
    "\n",
    "        for i, v in enumerate(prices): dc[v - i] += v\n",
    "\n",
    "        return max(dc.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "        mp = defaultdict(int)\n",
    "        for i, v in enumerate(prices):\n",
    "            mp[v - i] += v\n",
    "        return max(mp.values(), default=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "\n",
    "\n",
    "        # prices[indexes[j]] - prices[indexes[j - 1]] == indexes[j] - indexes[j - 1]\n",
    "        # prices[indexes[j]] - indexes[j] = prices[indexes[j - 1]] - indexes[j - 1]\n",
    "\n",
    "        n = len(prices)\n",
    "        minusDict = collections.defaultdict(int)\n",
    "        for i, p in enumerate(prices):\n",
    "            minusDict[p - i] += p\n",
    "\n",
    "        return max(minusDict.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    1-indexed prices\n",
    "    - 这是第i天某只股票的价格，任务是线性地选择\n",
    "    - prices[indexes[j]] - prices[indexes[j - 1]] == indexes[j] - indexes[j - 1]\n",
    "    我们的选择一组indexes\n",
    "    - 使得斜率保持一致，且是递增的，然后我们要做到极致的得分\n",
    "    - 可以用DP吗\n",
    "        - 以某个数为结尾的最大值，但是我们怎么知道，\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "        cnt = Counter()\n",
    "        for i, v in enumerate(prices):\n",
    "            cnt[v - i] += v\n",
    "        return max(cnt.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "        dc = Counter()\n",
    "        for i,v in enumerate(prices): dc[v-i] += v\n",
    "        return max(dc.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "        dc = Counter()\n",
    "        for i,v in enumerate(prices): dc[v-i] += v\n",
    "        return max(dc.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        v = [prices[i] - i - 1 for i in range(n)]\n",
    "        ans,c = 0,defaultdict(int)\n",
    "        for i in range(n):\n",
    "            c[v[i]] += prices[i]\n",
    "            ans = max(ans,c[v[i]])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, prices: List[int]) -> int:\n",
    "        a = [prices[i - 1] - i for i in range(1, 1 + len(prices))]\n",
    "        #print(f'{a=}')\n",
    "        d = collections.defaultdict(int)\n",
    "        for i in range(len(prices)):\n",
    "            d[a[i]] += prices[i]\n",
    "        #print(f'{d=}')\n",
    "        return max(d.values())"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
